package 剑指offer第2版;

import java.util.ArrayList;
import java.util.List;

public class 剑指Offer和为s的连续正数序列 {

    /**
     * 设连续正整数序列的左边界i和右边界j，则可构建滑动窗口从左向右滑动。循环中，每轮判断滑动窗口内元素与目标值target的大小关系，若相等则记录结果，若大于target则移动左边界i（以减小窗口内的元素和），若小于target则移动有边界j（以增大窗口内的元素和）
     * - 算法流程：
     * 	- 1，初始化：左边界i=1，有边界j=2，元素和s=3，结果列表res；
     * 	- 2，循环：当i>=j时跳出
     * 		- 当s>target时：向右移动左边界i=i+1，并更新元素和s；
     * 		- 当s<target时：向右移动右边界j=j+1，并更新元素和s;
     * 		- 当s=target时：记录连续整数序列，并向右移动左边界i=i+1;
     * @param target
     * @return
     */
    public static int[][] findContinuousSequence(int target) {
        List<int[]> list=new ArrayList<>();
        int i=1,j=2;
        int s=3;
        while (i<j){
            if(s<target) {
                j++;
                s=0;
                for (int k = i; k <= j; k++) {
                    s+=k;
                }
            }else if(s>target){
                i++;
                s=0;
                for (int k = i; k <= j; k++) {
                    s+=k;
                }
            }else {
                int[]a=new int[j-i+1];
                s=0;
                int index=0;
                for (int k = i; k <= j; k++) {
                    a[index++]=k;
                    s+=k;
                }
                list.add(a);
                s-=i;
                i++;
            }
        }
        return list.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        int[][] continuousSequence = findContinuousSequence(9);
        System.out.println(continuousSequence.length);
    }
}


